#include <iostream>
#include "string.h"

using namespace std;

//*******PMT generator
void generatePMT(char *pin_str,int *presult,int len_str){ //len_str is the strlen;
    int res_str[len_str+1]={0};
    int i=0,j;
    res_str[0]=-1;
    for(j=1;pin_str[j]!='\0';j++){
        if(pin_str[j]==pin_str[i]){
            res_str[j]=++i; //
        }else{
            res_str[j]=-1;
            i=0;
        }
    }
    for(i=0;i<len_str;i++)
        presult[i]=res_str[i];
}

int KMP(char *string,char *pattern,int len_pattern){    //len_str is the real length, i.e. '\0' is not included.

    //**************************generate PMT
    int PMT[len_pattern+1]={0};
    generatePMT(pattern,PMT,len_pattern);
    //******Start to match***
    int i,j=0;    //The length of substring that has been matched
    for(i=0;string[i+1]!='\0';i++){
        if(string[i]==pattern[j]){
            while(pattern[j+1]!='\0' && string[i+1]!='\0'){
                if(pattern[j]!=string[i]){
                    j-=PMT[!j?0:j-1]==-1?0:PMT[!j?0:j-1];
                    break;
                }
                ++j,++i;
            }
            if(pattern[j+1]=='\0')    return i-j;
            //if break then the program would get back to the outer loop
        }
    }
    return -1;
}

int main(int argc, char const *argv[])
{
    char string[]="abababcd";
    char pattern[]="cd";
    int result[strlen(pattern)+1]={0};
    generatePMT(pattern,result,strlen(pattern));
    for(int i=0;result[i]!='\0';i++)
        cout <<  (int)result[i] << " ";
    cout << endl << KMP(string,pattern,strlen(pattern)) << endl;
}
